home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 08 - 1992 / 08.02 Jun 92 / Generic Virus Detection / BoyerMoore.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-26  |  8.0 KB  |  261 lines  |  [TEXT/MPS ]
  1. /* BoyerMoore.c — Functions for fast, variable- randomized virus infection detection.
  2.     Copyright © 1992 by William H. Hsu.
  3.     Think C version.
  4.  
  5.     Notes:
  6.     •    As explained in the dynamic algorithm code, these routines are tolerant toward a wide variety of variations, including padded and mutating viral code
  7.  
  8. /* byrmoore.c: main searching file */
  9.  
  10. #include "bmdec.h"
  11. void boyer_moore()
  12. {
  13.   FILE *my_file;
  14.   char n[MAXSIZE], *sub_string, **pattern_array;
  15.   int text_length, i, j, sum, match_count, size,         divisor, total_match, index, index2, vdat_count,         refNum, files_to_scan = 5, total_virus_length;
  16.   int *pattern_length_array, *pattern_index_array;    /* virus segment lengths and delimiters */
  17.   long file_size, total_file_size;
  18.   register Handle rsrc, rsrc2;
  19. /* Note: the code which scans files in the same way that Disinfectant does is far too long to include in this article.  The array used below is for the purpose of example only.  John Norstad has made the enumeration part of his program publicly available (by FTP at acns.nwu.edu) */
  20.   Str255 ResFileArray[5] = {"\pOne*", "\pTwo*",         "\pThree", "\pFour", "\pFive"};
  21.   Str255 DescriptionArray[5] = {"File 1\t", "File 2\t",         "File 3\t", "File 4\t", "File 5\t"};
  22.   ResType typeName;
  23.   short resCount, typeCount, resCount2;
  24.   srand((unsigned)time(NULL));
  25.   ToolBoxInit();
  26.   open_file (&my_file, WRITE_MODE);
  27.   csettabs (TABS, stdout);
  28. #ifdef _REPORT
  29.   printf("File description\t\t\tScore\tFile size\tAlgorithm's Decision\n");
  30.     printf("================\t\t\t=====\t=========\t====================\n\n");
  31.   fprintf(my_file, "File description\t\t\tScore\tFile size\tAlgorithm's Decision\n");
  32.   fprintf(my_file, "================\t\t\t=====\t=========\t====================\n\n");
  33. #endif
  34.   sub_string = (char *)calloc(SIZE, sizeof(char));
  35.   CurResFile();
  36.   resCount = Count1Resources ('VDAT');
  37.   vdat_count = resCount;
  38.   pattern_length_array = (int *)calloc(resCount,         sizeof(int));
  39.   pattern_index_array = (int *)calloc(resCount,         sizeof(int));
  40.   pattern_array = (char **)calloc(resCount, 
  41.         sizeof(char *));
  42.   while (resCount)    /* loop resCount down to 1 */
  43.   {    /* get handle, but don't load it */
  44.     rsrc = Get1IndResource ('VDAT', resCount);
  45.     index = SizeResource (rsrc);
  46.     HLock (rsrc);
  47.     pattern_array[resCount-1] = (char *)                 calloc(index, sizeof(char));
  48.     pattern_length_array[resCount-1] = copy_array             (*rsrc, pattern_array[resCount-1], &index);
  49.     pattern_index_array[resCount-1] = ((resCount <             vdat_count) ? (pattern_length_array[resCount-            1] + pattern_index_array[resCount]) :             pattern_length_array[resCount-1]);
  50.     HUnlock (rsrc);
  51.     --resCount;
  52.   }
  53.   total_virus_length = pattern_index_array[0];
  54.  
  55.   SetResLoad (true);
  56.   for (i = 0; i < files_to_scan; i++)
  57.   {
  58.     refNum = OpenResFile (ResFileArray[i]);
  59.     match_count = 0;
  60.     divisor = 0;
  61.     for (j = 0; j < ITERATIONS; j++)
  62.     {
  63.       total_file_size = 0;
  64.       sum = 0;
  65.       while (!random_string(pattern_array,                     sub_string, pattern_index_array,                     total_virus_length, SIZE, vdat_count));
  66.       typeCount = Count1Types ();
  67.       while (typeCount)
  68.       {
  69.         Get1IndType (&typeName, typeCount);
  70.         resCount2 = Count1Resources (typeName);
  71.         while (resCount2)
  72.         {
  73.           rsrc2 = Get1IndResource (typeName,                         resCount2);
  74.           index2 = SizeResource (rsrc2);
  75.           file_size = 0;
  76.           HLock (rsrc2);
  77.                     while (text_length = copy_array (*rsrc2,                             n, &index2))
  78.           {
  79.             compare(sub_string, n, SIZE,                                     text_length, &sum);
  80.             file_size += text_length;
  81.           }
  82.           HUnlock (rsrc2);
  83.           total_file_size += file_size;
  84.           --resCount2;
  85.         }
  86.         --typeCount;
  87.       }
  88.       divisor++;
  89.       if (sum)
  90.         match_count++;
  91.     }
  92. #  ifdef _REPORT
  93.     printf("%s\t\t", DescriptionArray[i]);
  94.     fprintf(my_file, "%s\t\t", DescriptionArray[i]);
  95.     printf("%d\t\t%ld\t", match_count, total_file_size);
  96.     fprintf(my_file, "%d\t\t%ld\t", match_count,             total_file_size);
  97. #    endif
  98.     if (match_count >= (divisor/LIMIT))
  99.     {
  100. #    ifdef _REPORT
  101.       printf("\t%s\n", INFECTED_STRING);
  102.       fprintf(my_file, "\t%s\n", INFECTED_STRING);
  103. #    endif
  104.     }
  105.     else
  106.     {
  107. #    ifdef _REPORT
  108.       printf("\t%s\n", CLEAN_STRING);
  109.       fprintf(my_file, "\t%s\n", CLEAN_STRING);
  110. #    endif
  111.     }
  112.     CloseResFile(refNum);
  113.   }
  114.   printf("\nScore represents matches out of %d,         with %d needed to diagnose infection.\n",         divisor, divisor/LIMIT);
  115.   fprintf(my_file, "\nScore represents matches out         of %d, with %d needed to diagnose             infection.\n", divisor, divisor/LIMIT);
  116.   free(sub_string);
  117.   fclose(my_file);
  118. }
  119.  
  120. char random_string(string_array, sub_string, index_array, length, substring_length, vdat_count)
  121. char **string_array, sub_string[];
  122. int index_array[], length, substring_length, vdat_count;
  123. {
  124.   int location, segment, i, zero_count = 0;
  125.   Boolean legal = false, In_The_Right_Segment =         false;   /* length and segments okay? */
  126.   segment = vdat_count-1;
  127.   while (!legal)
  128.   {
  129.     location = (int)((rand()/(double)MAXINT)*             (length - substring_length));
  130.     In_The_Right_Segment = false;
  131.     while (!In_The_Right_Segment)
  132.     {
  133.       if (location <= index_array[segment])
  134.       {
  135.         In_The_Right_Segment = true;
  136.         if (location <= (index_array[segment] -                     substring_length + 1))
  137.           legal = true;
  138.         else
  139.           legal = false;
  140.       }
  141.       else
  142.         segment--;
  143.     }
  144.   }
  145.   if (segment < vdat_count-1)
  146.     location -= index_array[segment+1];
  147.   for (i = location; i < location +             substring_length; i++)
  148.   {
  149.     sub_string[i-location] =                                         (string_array[segment])[i];
  150.     if (!string_array[segment][i])
  151.       zero_count++;
  152.   }
  153.   if (zero_count < substring_length/2) 
  154.     return(TRUE);
  155.   else
  156.     return(FALSE);
  157. }
  158.  
  159. /* compare: the heart of the Boyer-Moore heurstic, similar to Knuth-Morris-Pratt's matching engine */
  160. void compare(p, t, pattern_length, text_length, sum)
  161. char *p, *t;
  162. int pattern_length, text_length, *sum;
  163. {
  164.   ALPHABET_ARRAY char_jump;
  165.   int *match_jumps, print;
  166.   allocate_array(&match_jumps, pattern_length);
  167.   compute_jumps(p, char_jump, pattern_length-1);
  168.   compute_match_jumps(p, &match_jumps,             pattern_length);
  169.   if (bm_match(p, t, char_jump, match_jumps,         pattern_length, text_length))
  170.     (*sum)++;
  171.   free(match_jumps);
  172. }
  173.  
  174. void allocate_array(array, size)
  175. INDEX_ARRAY array;
  176. int size;
  177. {
  178.   *array = (int *)calloc(size, sizeof(int));
  179. }
  180.  
  181. /* the bad-character failure function
  182. NOTE: if the ASCII alphabet, which has size 256, is
  183. used, this function is not worth computing for resource text strings of length ≤ 256 */
  184. void compute_jumps(p, char_jump, length)
  185. char *p;
  186. ALPHABET_ARRAY char_jump;
  187. int length;
  188. {
  189.   int c, k;
  190.   for (c = 0; c < CHARS; c++)
  191.     char_jump[c] = length;
  192.   for (k = 0; k < length; k++)
  193.     char_jump[POSITIVE(p[k])] = length-k-1;
  194. }
  195.  
  196. /* implementation of pseudocode from [Baase 88] 
  197.    — uses the good-suffix failure function */
  198. void compute_match_jumps(p, match_jump, pattern_length)
  199. char *p;
  200. INDEX_ARRAY match_jump;
  201. int pattern_length;
  202. {
  203.   int m, k, q, qq;
  204.   int *back;
  205.   allocate_array(&back, pattern_length+1);
  206.   m = pattern_length;
  207.   for (k = 0; k < m; k++)
  208.     (*match_jump)[k] = 2*m-k-1;
  209.   q = m;
  210.   for (k = m-1; k >= 0; k--)
  211.   {
  212.     back[k] = q;
  213.     while ((q < m) && (p[k] != p[q]))
  214.     {
  215.       (*match_jump)[q] = MIN2((*match_jump)[q], m-                k-1);
  216.       q = back[q];
  217.     }
  218.     q--;
  219.   }
  220.   for (k = 0; k < q; k++)
  221.     (*match_jump)[k] = MIN2((*match_jump)[k], m+q-            k-1);
  222.   qq = back[q];
  223.   while (q < m)
  224.   {
  225.     while (q < qq)
  226.     {
  227.       (*match_jump)[q] = MIN2((*match_jump)[q], qq-                q+m-1);
  228.       q++;
  229.     }
  230.     qq = back[qq];
  231.   }
  232.   free(back);
  233. }
  234.  
  235. int bm_match(p, t, char_jump, match_jump, pattern_length, text_length)
  236. char *p, *t;
  237. ALPHABET_ARRAY char_jump;
  238. int *match_jump, pattern_length, text_length;
  239. {
  240.   int j, k; /* j indexes text characters; k indexes                                 the pattern */
  241.   j = pattern_length - 1;
  242.   k = j;
  243.   while (j < text_length)
  244.   {
  245.     if (k == -1)
  246.       return(TRUE);
  247.     if (t[j] == p[k])
  248.     {
  249.       j--;
  250.       k--;
  251.     }
  252.     else
  253.     {
  254.       j += MAX2(char_jump[POSITIVE(t[j])],                 match_jump[k]);
  255.       k = pattern_length - 1;
  256.     }
  257.   }
  258.   return(FALSE);
  259. }
  260.  
  261.